package leetcode100

// TODO 双向链表+哈希表 [经典] 【-】 LRU 缓存
// TODO https://leetcode.cn/problems/lru-cache/solution/by-shi-zhi-wang-liao-6vmz/
// TODO 为什么使用双向循环链表而不是单链表: 链表的节点需要在LRU中频繁插入和删除，双向链表可以快速地进行这些操作
// TODO 注意事项: 虚拟头结点 和 尾结点: 都是必要的

type LRUCache struct {
	DoubleNode DoubleNode
	CacheMap   map[int]*Node
	cap        int
}

func Constructor(capacity int) LRUCache {
	lRUCache := LRUCache{
		cap:        capacity,
		DoubleNode: *NewDoubleNode(), // NewDoubleNode() 反悔的是一个地址, 所以需要加*
		CacheMap:   make(map[int]*Node),
	}
	return lRUCache
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.CacheMap[key]; !ok {
		return -1
	} else {
		this.Put(key, node.val)
		return node.val
	}
}

func (this *LRUCache) Put(key int, value int) {
	node := &Node{
		key: key,
		val: value,
	}
	if oldNode, ok := this.CacheMap[key]; ok {
		// 移除旧结点, 放入队列尾部, 则变成新结点
		this.DoubleNode.Remove(oldNode)
		delete(this.CacheMap, key)
	} else {
		if this.cap == this.DoubleNode.Len() {
			frist := this.DoubleNode.RemoveFirst()
			delete(this.CacheMap, frist.key)
		}
	}
	this.CacheMap[key] = node
	this.DoubleNode.PutLast(node)
}

type Node struct {
	Prev, Next *Node
	key, val   int
}

type DoubleNode struct {
	Head, Tail *Node
	Size       int
}

// 初始化
func NewDoubleNode() *DoubleNode {
	doubleNode := &DoubleNode{}
	doubleNode.Tail = &Node{}
	doubleNode.Head = &Node{}
	doubleNode.Tail.Prev = doubleNode.Head
	doubleNode.Head.Next = doubleNode.Tail
	return doubleNode
}

// 往末尾节点插入
func (this *DoubleNode) PutLast(node *Node) {
	node.Next = this.Tail
	node.Prev = this.Tail.Prev
	this.Tail.Prev.Next = node
	this.Tail.Prev = node
	this.Size++
}

// 删除一个节点
func (this *DoubleNode) Remove(node *Node) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
	this.Size--
}

// 移除并返回头节点
func (this *DoubleNode) RemoveFirst() *Node {
	if this.Head.Next == this.Tail {
		return nil
	}
	first := this.Head.Next
	this.Remove(first)
	return first
}

// 长度
func (this *DoubleNode) Len() int {
	return this.Size
}
